#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/10/24 11:07|11:07
# @Author  : yangdingyi
# @File    : 2020-10-24.1024.视频拼接
# @Software: PyCharm
from tools.my_methods import *


class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        dp = [0] + [float("inf")] * T
        for i in range(1, T + 1):
            for aj, bj in clips:
                if aj < i <= bj:
                    dp[i] = min(dp[i], dp[aj] + 1)

        return -1 if dp[T] == float("inf") else dp[T]
